Hài lòng trước những chiến tích thu được của đội lính mộ Bắc kỳ trong các trận giao tranh hồi tháng 3 và 4 năm 1884, tướng Millot quyết định chính thức hóa các đơn vị này bằng cách thành lập hai trung đoàn lính mộ Bắc kỳ tirailleurs (tức bộ binh, hay còn gọi là lính khố đỏ, mỗi trung đoàn gồm 3.000 quân, tổ chức thành ba tiểu đoàn, mỗi tiểu đoàn gồm 4 đại đội, mỗi đại đội có 250 lính, chỉ huy bởi các sĩ quan hải quân đánh bộ giàu kinh nghiệm. Mô hình này được sử dụng mấy năm trước tại Nam kỳ, nay được áp dụng cho các trung đoàn lính mộ Bắc kỳ. Theo sắc lệnh ngày 12 tháng 5 năm 1884, tướng Millot thành lập các trung đoàn bộ binh Bắc kỳ số 1 và 2. Các trung đoàn này được chỉ huy bởi Trung tá de Maussion và Trung tá Berger, là hai sĩ quan kỳ cựu, có nhiều chiến công trong các chiến dịch mà các tướng Bouët và Courbet chỉ huy. Các tiểu đoàn trưởng dưới quyền họ là Tonnot, Jorna de Lacale, Lafont, Merlaud, Pelletier và Pizon.[1]

Do không có đủ sĩ quan hải quân đánh bộ chỉ huy, hai trung đoàn này ban đầu không được thành lập với đầy đủ quân số. Trong vài tháng, các đơn vị này chỉ gồm 9 đại đội, chia làm hai tiểu đoàn.[1] Tuy nhiên, việc tuyển quân vẫn tiếp tục trong suốt mùa hè năm 1884 và tới 30 tháng 10 cả hai trung đoàn này đã đạt đủ quân số 3.000 người.[3]

Một phương thức được tướng Millot thực hiện để đẩy nhanh việc tuyển quân là sử dụng lính đào ngũ từ quân cờ đen. Có khoảng vài trăm quân cờ đen đầu hàng Pháp tháng 7 năm 1884, sau khi quân Pháp hạ thành Hưng Hóa và Tuyên Quang, và xin được phục vụ quân Pháp. Tướng Millot cho phép họ nhập vào các trung đoàn lính mộ Bắc kỳ như một đại đội độc lập, và họ được phái đến một đồn lẻ của Pháp trên sông Đáy dưới quyền chỉ huy của một sĩ quan Pháp có thiện cảm với họ, Thiếu úy Bohin. Nhiều sĩ quan Pháp khác tỏ ra hoảng sợ trước việc tướng Millot sẵn lòng tin tưởng quân cờ đen, và Bohin được mệnh danh là le condamné à mort - tức coi như đã chết. Trên thực tế, quân cờ đen đáp lại sự tử tế của thiếu úy, và trong vòng vài tháng, phục vụ tốt dưới trướng ông này, tham gia một số cuộc càn quét quân nổi dậy người Việt và giặc cướp. Tuy nhiên, trong đêm ngày 25 tháng 12 năm 1884, họ đào ngũ hàng loạt, mang theo vũ khí, quân trang quân dụng và bỏ chạy về phía sông Đà. Họ cũng giết một trung sỹ người Bắc kỳ khi người này định báo động, nhưng không đụng đến thiếu úy Bohin đang ngủ say. Có lẽ là họ bị chấn động trước ưu thế của quân Thanh trên chiến trường Bắc kỳ, và mất lòng tin vào khả năng chiến thắng của quân Pháp, nên quyết định gia nhập trở lại vào hàng ngũ quân Cờ đen, rồi tham gia trong trận Tuyên Quang. Thí nghiệm thất bại của tướng Millot không được người kế nhiệm ông là tướng Brière de l'Isle lặp lại, và người Pháp từ đó về sau không tìm cách sáp nhập quân Cờ đen vào thành phần các trung đoàn bộ binh Bắc kỳ nữa.

Trung đoàn bộ binh Bắc kỳ thứ ba được Tướng de Courcy thành lập bởi sắc lệnh ra ngày 28 tháng 7 năm 1885. Trung đoàn thứ tư được Tướng Warnet thành lập với sắc lệnh ngày 19 tháng 2 năm 1886.[4]